課程資訊
課程名稱
 最佳化演算法
Optimization Algorithms 
開課學期
 108-1 
授課對象
 理學院  應用數學科學研究所  
授課教師
 李彥寰 
課號
 CSIE5410 
課程識別碼
 922 U4500 
班次
  
學分
 3.0 
全/半年
 半年 
必/選修
 選修 
上課時間
 星期一7,8,9(14:20~17:20) 
上課地點
 綜501 
備註
 總人數上限：50人 
  
課程簡介影片
 
核心能力關聯
 核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

This is a theory course that requires math maturity and does not have any programming assignment!!!

Optimization has become a prevalent tool in modern algorithm design. In this course, we will study optimization algorithms from the perspective of machine learning theory. We will focus on the black-box approach; that is, we consider accessing information about the function to be optimized via an oracle, and derive non-asymptotic worst-case oracle complexity bounds with respect to a given class of objective functions.

This course consists of two parts. The first part introduces basic notions in convex analysis, and standard convex optimization algorithms. The second part focuses on online optimization algorithms, which allow one to do model-free sequential predictions, and can be computationally efficient when the data size is large. 

課程目標
 After taking this course, the students are expected to have the ability to:
．Characterize the pros and cons of an optimization algorithm.
．Choose an appropriate optimization algorithm for a given application scenario.
．Do basic complexity analyses of optimization algorithms.
．Read advanced literature in optimization and algorithm design. 
課程要求
 Prerequisites: Calculus, linear algebra, and probability.

Knowledge in convex analysis, statistics, and/or machine learning can be helpful but not necessary. 
預期每週課後學習時數
  
Office Hours
 備註： After class every week. TA hours TBA.  
指定閱讀
 A recommended reading list will be provided for every lecture.  
參考書目
 1. Yu. Nesterov. 2004. Introductory Lectures on Convex Optimization.
2. S. Bubeck. 2015. Convex Optimization: Algorithms and Complexity. (Available online: http://sbubeck.com/Bubeck15.pdf)
3. A. Ben-Tal and A. Nemirovski. 2015. Lectures on Modern Convex Optimization.(Available online: http://www2.isye.gatech.edu/~nemirovs/LMCO_LN.pdf)
4. N. Cesa-Bianchi and G. Lugosi. 2006. Prediction, Learning, and Games.
5. S. Bubeck. 2011. Introduction to Online Optimization. (Available online: http://sbubeck.com/BubeckLectureNotes.pdf)
6. S. Shalev-Shwartz. 2012. Online Learning and Online Convex Optimization.
7. E. Hazan. 2016. Introduction to Online Convex Optimization. (Available online: http://ocobook.cs.princeton.edu/) 
評量方式
(僅供參考)
  
No.
項目
百分比
說明
1. 
 Homework 
40% 
  
2. 
 Midterm exam 
20% 
  
3. 
 Final project 
40% 
  
 
課程進度
週次
日期
單元主題
第1週
 9/09  Basic concepts.  
第2週
 9/16  Convexity.  
第3週
 9/23  Gradient descent.  
第4週
 9/30  Accelerated gradient descent. Mirror descent.  
第5週
 10/07  Mirror descent. Subdifferential.  
第6週
 10/14  Composite minimization.  
第7週
 10/21  Composite minimization.  
第8週
 10/28  Composite minimization.  
第9週
 11/04  No class.  
第10週
 11/11  Proximal gradient method.  
第11週
 11/18  Midterm exam.  
第12週
 11/25  Frank-Wolfe method.  
第13週
 12/02  Online learning & optimization.  
第14週
 12/09  No class.  
第15週
 12/16  Learning in games.  
第16週
 12/23  Learning in games. Follow-the-leader-type methods.  
第17週
 12/30  Optimisitic methods. Accelerated gradient descent revisited.